Groth16 Slides
Groth16 A successor to Pinocchio Proofs are 3 elements, rather than 8 Verification is 3 pairings, rather than 12 Trusted Setup α , β , τ , γ , δ ← random scalars [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) δ , τ n − 3 t ( τ ) δ , . . . , τ t ( τ ) δ , t ( τ ) δ ] ← SRS for h ( τ ) t ( τ ) \begin{aligned}
\alpha,\beta,\tau,\gamma,\delta &\leftarrow& \text{random scalars}\\
[\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow& \text{SRS for } \mathbb{G}_1\\
[\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow& \text{SRS for } \mathbb{G}_2\\
\\
[\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow&\text{SRS for } h(\tau)t(\tau)\\
\\
\end{aligned} α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) , δ τ n − 3 t ( τ ) , ... , δ τ t ( τ ) , δ t ( τ ) ] ← ← ← ← random scalars SRS for G 1 SRS for G 2 SRS for h ( τ ) t ( τ ) Used with public portion of witness [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ G 1 [ Ψ 2 ] 1 = α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) γ G 1 ⋮ [ Ψ l ] 1 = α v l ( τ ) + β u l ( τ ) + w l ( τ ) γ G 1 Used with private portion of witness [ Ψ l + 1 ] 1 = α v l + 1 ( τ ) + β u l + 1 ( 1 τ ) + w l + 1 ( τ ) δ G 1 [ Ψ l + 2 ] 1 = α v l + 2 ( τ ) + β u l + 2 ( τ ) + w l + 2 ( τ ) δ G 1 ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ G 1 \begin{aligned}
&&\text{Used with public portion of witness}\\
[\Psi_1]_1&=&\frac{\alpha v_1(\tau)+\beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\
[\Psi_2]_1&=&\frac{\alpha v_2(\tau)+\beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\
\vdots&&\\
[\Psi_l]_1&=&\frac{\alpha v_l(\tau)+\beta u_l(\tau) + w_l(\tau)}{\gamma}G_1\\
\\
&&\text{Used with private portion of witness}\\
[\Psi_{l+1}]_1&=&\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(1\tau) + w_{l+1}(\tau)}{\delta}G_1\\
[\Psi_{l+2}]_1&=&\frac{\alpha v_{l+2}(\tau)+\beta u_{l+2}(\tau) + w_{l+2}(\tau)}{\delta}G_1\\
\vdots&&\\
[\Psi_m]_1&=&\frac{\alpha v_m(\tau)+\beta u_m(\tau) + w_m(\tau)}{\delta}G_1\\
\end{aligned} [ Ψ 1 ] 1 [ Ψ 2 ] 1 ⋮ [ Ψ l ] 1 [ Ψ l + 1 ] 1 [ Ψ l + 2 ] 1 ⋮ [ Ψ m ] 1 = = = = = = Used with public portion of witness γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) G 1 γ α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) G 1 γ α v l ( τ ) + β u l ( τ ) + w l ( τ ) G 1 Used with private portion of witness δ α v l + 1 ( τ ) + β u l + 1 ( 1 τ ) + w l + 1 ( τ ) G 1 δ α v l + 2 ( τ ) + β u l + 2 ( τ ) + w l + 2 ( τ ) G 1 δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 1 Publishes ( [ α ] 1 , [ β ] 1 [ β ] 2 , [ γ ] 2 , [ δ ] 1 [ δ ] 2 , S R S G 1 , S R S G 2 , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , . . . , [ Ψ m ] 1 ) ([\alpha]_1,\ [\beta]_1[\beta]_2,\ [\gamma]_2,\ [\delta]_1[\delta]_2,\ SRS_{G_1},\ SRS_{G_2},\ [\Psi_1]_1,\ [\Psi_2]_1,\ ..., [\Psi_m]_1) ([ α ] 1 , [ β ] 1 [ β ] 2 , [ γ ] 2 , [ δ ] 1 [ δ ] 2 , SR S G 1 , SR S G 2 , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , ... , [ Ψ m ] 1 )
Base Trusted Setup τ ← random scalar, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , . . . , τ t ( τ ) , t ( τ ) ] ← SRS for h ( τ ) t ( τ ) Publishes [ S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) ] Prover [ A ] 1 = ∑ i = 1 m a i u ( τ ) [ B ] 2 = ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = 1 m a i w ( τ ) + h ( τ ) t ( τ ) Verifier [ A ] 1 ∙ [ B ] 2 = ? [ C ] 1 ∙ [ G ] 2 \begin{aligned}
\text{Trusted Setup}\\
\tau &\leftarrow \text{random scalar, toxic waste}\\
[\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\
[\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\
[\tau^{n-2}t(\tau),\ \tau^{n-3}t(\tau),\ ...,\ \tau t(\tau),\ t(\tau)] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\
\\
\text{Publishes}\\
[SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}]\\
\\
\text{Prover}\\
[A]_1&=\sum^m_{i=1}a_iu(\tau)\\
[B]_2&=\sum^m_{i=1}a_iv(\tau)\\
[C]_1&=\sum^m_{i=1}a_iw(\tau)+h(\tau)t(\tau)\\
\\
\text{Verifier}\\
[A]_1\bullet[B]_2&\stackrel{?}{=}[C]_1\bullet[G]_2\\
\end{aligned} Trusted Setup τ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , ... , τ t ( τ ) , t ( τ )] Publishes [ SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ A ] 1 ∙ [ B ] 2 ← random scalar, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) G 2 , SR S h ( τ ) t ( τ ) ] = i = 1 ∑ m a i u ( τ ) = i = 1 ∑ m a i v ( τ ) = i = 1 ∑ m a i w ( τ ) + h ( τ ) t ( τ ) = ? [ C ] 1 ∙ [ G ] 2 Soundness Trusted Setup α , β , τ ← random scalars, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , . . . , τ t ( τ ) , t ( τ ) ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) Publishes ( [ α ] 1 , [ β ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) Verifier [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ [ G ] 2 \begin{aligned}
\text{Trusted Setup}\\
\alpha,\beta,\tau &\leftarrow \text{random scalars, toxic waste}\\
[\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\
[\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\
[\tau^{n-2}t(\tau),\ \tau^{n-3}t(\tau),\ ...,\ \tau t(\tau),\ t(\tau)] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\
\\
[\Psi_1]_1&=\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)\\
&\vdots\\
[\Psi_m]_1&=\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)\\
\\
\text{Publishes}\\
([\alpha]_1, [\beta]_2, SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\
\\
\text{Prover}\\
[A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau)\\
[B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau)\\
[C]_1&=\sum^m_{i=1}a_i[\Psi]_i+h(\tau)t(\tau)\\
\\
\text{Verifier}\\
[A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet[G]_2\\
\end{aligned} Trusted Setup α , β , τ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , ... , τ t ( τ ) , t ( τ )] [ Ψ 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 2 , SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ A ] 1 ∙ [ B ] 2 ← random scalars, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) = [ α ] 1 + i = 1 ∑ m a i u ( τ ) = [ β ] 2 + i = 1 ∑ m a i v ( τ ) = i = 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ [ G ] 2 Part-public witness Trusted Setup α , β , τ ← random scalars, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , . . . , τ t ( τ ) , t ( τ ) ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) Publishes ( [ α ] 1 , [ β ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = l + 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) Verifier [ X ] 1 = ∑ i = 1 l a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ G ] 2 + [ C ] 1 ∙ [ G ] 2 \begin{aligned}
\text{Trusted Setup}\\
\alpha,\beta,\tau &\leftarrow \text{random scalars, toxic waste}\\
[\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\
[\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\
[\tau^{n-2}t(\tau),\ \tau^{n-3}t(\tau),\ ...,\ \tau t(\tau),\ t(\tau)] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\
\\
[\Psi_1]_1&=\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)\\
&\vdots\\
[\Psi_m]_1&=\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)\\
\\
\text{Publishes}\\
([\alpha]_1, [\beta]_2, SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\
\\
\text{Prover}\\
[A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau)\\
[B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau)\\
[C]_1&=\sum^m_{i=l+1}a_i[\Psi]_i+h(\tau)t(\tau)\\
\\
\text{Verifier}\\
[X]_1 &= \sum^l_{i=1}a_i\Psi_i\\
[A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [X]_1 \bullet [G]_2 + [C]_1\bullet[G]_2\\
\end{aligned} Trusted Setup α , β , τ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) , τ n − 3 t ( τ ) , ... , τ t ( τ ) , t ( τ )] [ Ψ 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 2 , SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ X ] 1 [ A ] 1 ∙ [ B ] 2 ← random scalars, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) = [ α ] 1 + i = 1 ∑ m a i u ( τ ) = [ β ] 2 + i = 1 ∑ m a i v ( τ ) = i = l + 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) = i = 1 ∑ l a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ G ] 2 + [ C ] 1 ∙ [ G ] 2 Fixing soundness Trusted Setup α , β , τ , γ , δ ← random scalars, toxic waste [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) δ , τ n − 3 t ( τ ) δ , . . . , τ t ( τ ) δ , t ( τ ) δ ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ ⋮ [ Ψ l ] 1 = α v l ( τ ) + β u l ( τ ) + w l ( τ ) γ [ Ψ l + 1 ] 1 = α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) δ ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ Publishes ( [ α ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) [ C ] 1 = ∑ i = l + 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) Verifier [ X ] 1 = ∑ i = 1 l a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 \begin{aligned}
\text{Trusted Setup}\\
\alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{random scalars, toxic waste}\\
[\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\
[\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\
[\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\
\\
[\Psi_1]_1&=\frac{\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)}{\gamma}\\
&\vdots\\
[\Psi_l]_1&=\frac{\alpha v_l(\tau)+\beta u_l(\tau)+w_l(\tau)}{\gamma}\\
[\Psi_l+1]_1&=\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(\tau)+w_{l+1}(\tau)}{\delta}\\
&\vdots\\
[\Psi_m]_1&=\frac{\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)}{\delta}\\
\\
\text{Publishes}\\
([\alpha]_1, [\beta]_2, [\gamma]_2, [\delta]_2, SRS_{\mathbb{G}_1}, SRS&_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\
\\
\text{Prover}\\
[A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau)\\
[B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau)\\
[C]_1&=\sum^m_{i=l+1}a_i[\Psi]_i+h(\tau)t(\tau)\\
\\
\text{Verifier}\\
[X]_1 &= \sum^l_{i=1}a_i\Psi_i\\
[A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [X]_1 \bullet [\gamma]_2 + [C]_1\bullet[\delta]_2\\
\end{aligned} Trusted Setup α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) , δ τ n − 3 t ( τ ) , ... , δ τ t ( τ ) , δ t ( τ ) ] [ Ψ 1 ] 1 [ Ψ l ] 1 [ Ψ l + 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 2 , SR S G 1 , SRS Prover [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ X ] 1 [ A ] 1 ∙ [ B ] 2 ← random scalars, toxic waste ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = γ α v l ( τ ) + β u l ( τ ) + w l ( τ ) = δ α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) ⋮ = δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) = [ α ] 1 + i = 1 ∑ m a i u ( τ ) = [ β ] 2 + i = 1 ∑ m a i v ( τ ) = i = l + 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) = i = 1 ∑ l a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 Enforcing Zero-Knowledge Trusted Setup α , β , τ , γ , δ ← random scalars [ τ n − 1 G 1 , τ n − 2 G 1 , . . . , τ G 1 , G 1 ] ← SRS for G 1 [ τ n − 1 G 2 , τ n − 2 G 2 , . . . , τ G 2 , G 2 ] ← SRS for G 2 [ τ n − 2 t ( τ ) δ , τ n − 3 t ( τ ) δ , . . . , τ t ( τ ) δ , t ( τ ) δ ] ← SRS for h ( τ ) t ( τ ) [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ ⋮ [ Ψ l ] 1 = α v l ( τ ) + β u l ( τ ) + w l ( τ ) γ [ Ψ l + 1 ] 1 = α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) δ ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ Publishes ( [ α ] 1 , [ β ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 1 , [ δ ] 2 , S R S G 1 , S R S G 2 , S R S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , . . . [ Ψ m ] 1 ) Prover r , s ← random scalars, toxic waste [ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u ( τ ) + r [ δ ] 1 [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v ( τ ) + s [ δ ] 1 [ C ] 1 = ∑ i = l + 1 m a i [ Ψ ] i + h ( τ ) t ( τ ) + [ A ] 1 s + [ B ] 1 r − r s [ δ ] 1 Verifier [ X ] 1 = ∑ i = 1 l a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 \begin{aligned}
\text{Trusted Setup}\\
\alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{random scalars}\\
[\tau^{n-1}G_1,\ \tau^{n-2}G_1,\ ...,\ \tau G_1,\ G_1] &\leftarrow \text{SRS for } \mathbb{G}_1\\
[\tau^{n-1}G_2,\ \tau^{n-2}G_2,\ ...,\ \tau G_2,\ G_2] &\leftarrow \text{SRS for } \mathbb{G}_2\\
[\frac{\tau^{n-2}t(\tau)}{\delta},\ \frac{\tau^{n-3}t(\tau)}{\delta},\ ...,\ \frac{\tau t(\tau)}{\delta},\ \frac{t(\tau)}{\delta}] &\leftarrow\text{SRS for } h(\tau)t(\tau)\\
\\
[\Psi_1]_1&=\frac{\alpha v_1(\tau)+\beta u_1(\tau)+w_1(\tau)}{\gamma}\\
&\vdots\\
[\Psi_l]_1&=\frac{\alpha v_l(\tau)+\beta u_l(\tau)+w_l(\tau)}{\gamma}\\
[\Psi_l+1]_1&=\frac{\alpha v_{l+1}(\tau)+\beta u_{l+1}(\tau)+w_{l+1}(\tau)}{\delta}\\
&\vdots\\
[\Psi_m]_1&=\frac{\alpha v_m(\tau)+\beta u_m(\tau)+w_m(\tau)}{\delta}\\
\\
\text{Publishes}\\
([\alpha]_1, [\beta]_1, [\beta]_2, [\gamma]_2, [\delta]_1, [\delta]_2,SRS_{\mathbb{G}_1}&, SRS_{\mathbb{G}_2}, SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,...[\Psi_m]_1)\\
\\
\text{Prover}\\
r,s &\leftarrow \text{random scalars, toxic waste}\\
[A]_1&=[\alpha]_1 + \sum^m_{i=1}a_iu(\tau) + r[\delta]_1\\
[B]_2&=[\beta]_2 + \sum^m_{i=1}a_iv(\tau) + s[\delta]_1\\
[C]_1&=\sum^m_{i=l+1}a_i[\Psi]_i+h(\tau)t(\tau) + [A]_1s + [B]_1r - rs[\delta]_1\\
\\
\text{Verifier}\\
[X]_1 &= \sum^l_{i=1}a_i\Psi_i\\
[A]_1\bullet[B]_2&\stackrel{?}{=} [\alpha]_1 \bullet [\beta]_2 + [X]_1 \bullet [\gamma]_2 + [C]_1\bullet[\delta]_2\\
\end{aligned} Trusted Setup α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , ... , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , ... , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) , δ τ n − 3 t ( τ ) , ... , δ τ t ( τ ) , δ t ( τ ) ] [ Ψ 1 ] 1 [ Ψ l ] 1 [ Ψ l + 1 ] 1 [ Ψ m ] 1 Publishes ([ α ] 1 , [ β ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 1 , [ δ ] 2 , SR S G 1 Prover r , s [ A ] 1 [ B ] 2 [ C ] 1 Verifier [ X ] 1 [ A ] 1 ∙ [ B ] 2 ← random scalars ← SRS for G 1 ← SRS for G 2 ← SRS for h ( τ ) t ( τ ) = γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ⋮ = γ α v l ( τ ) + β u l ( τ ) + w l ( τ ) = δ α v l + 1 ( τ ) + β u l + 1 ( τ ) + w l + 1 ( τ ) ⋮ = δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) , SR S G 2 , SR S h ( τ ) t ( τ ) , [ Ψ 1 ] 1 , ... [ Ψ m ] 1 ) ← random scalars, toxic waste = [ α ] 1 + i = 1 ∑ m a i u ( τ ) + r [ δ ] 1 = [ β ] 2 + i = 1 ∑ m a i v ( τ ) + s [ δ ] 1 = i = l + 1 ∑ m a i [ Ψ ] i + h ( τ ) t ( τ ) + [ A ] 1 s + [ B ] 1 r − rs [ δ ] 1 = i = 1 ∑ l a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 QAP Setup a ← witness vector O ← Output matrix L ← LHS Matrix R ← RHS Matrix O a = L a ⋅ R a ↓ O a → ∑ i = 1 m a i w i ( x ) → w ( x ) L a → ∑ i = 1 m a i u i ( x ) → u ( x ) R a → ∑ i = 1 m a i v i ( x ) → v ( x ) O a = L a ⋅ R a → w ( x ) = u ( x ) ⋅ v ( x ) + b ( x ) \begin{aligned}
a &\leftarrow \text{witness vector}\\
O &\leftarrow \text{Output matrix}\\
L &\leftarrow \text{LHS Matrix}\\
R &\leftarrow \text{RHS Matrix}\\
\\
Oa &=La\cdot Ra\\\\
& \big\downarrow\\\\
Oa &\rightarrow \sum_{i=1}^ma_iw_i(x) \rightarrow w(x)\\
La &\rightarrow \sum_{i=1}^ma_iu_i(x) \rightarrow u(x)\\
Ra &\rightarrow \sum_{i=1}^ma_iv_i(x) \rightarrow v(x)\\
Oa = La\cdot Ra &\rightarrow w(x) = u(x)\cdot v(x) + b(x)\\
\end{aligned} a O L R O a O a L a R a O a = L a ⋅ R a ← witness vector ← Output matrix ← LHS Matrix ← RHS Matrix = L a ⋅ R a ↓ ⏐ → i = 1 ∑ m a i w i ( x ) → w ( x ) → i = 1 ∑ m a i u i ( x ) → u ( x ) → i = 1 ∑ m a i v i ( x ) → v ( x ) → w ( x ) = u ( x ) ⋅ v ( x ) + b ( x )